|
In graph drawing, a universal point set of order ''n'' is a set ''S'' of points in the Euclidean plane with the property that every ''n''-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of ''S''. ==Bounds on the size of universal point sets== When ''n'' is ten or less, there exist universal point sets with exactly ''n'' points, but for all ''n'' ≥ 15 additional points are required.〔.〕 Several authors have shown that subsets of the integer lattice of size ''O''(''n'') × ''O''(''n'') are universal. In particular, showed that a grid of (2''n'' − 3) × (''n'' − 1) points is universal, and reduced this to a triangular subset of an (''n'' − 1) × (''n'' − 1) grid, with ''n''2/2 − ''O''(''n'') points. By modifying the method of de Fraysseix et al., found an embedding of any planar graph into a triangular subset of the grid consisting of 4''n''2/9 points. A universal point set in the form of a rectangular grid must have size at least ''n''/3 × ''n''/3〔; ; . A weaker quadratic lower bound on the grid size needed for planar graph drawing was given earlier by .〕 but this does not rule out the possibility of smaller universal point sets of other types. The smallest known universal point sets are not based on grids, but are instead constructed from superpatterns (permutations that contain all permutation patterns of a given size); the universal point sets constructed in this way have size ''n''2/4 − ''O''(''n'').〔.〕 proved the first nontrivial lower bound on the size of a universal point set, with a bound of the form ''n'' + Ω(√''n''), and showed that universal point sets must contain at least 1.098''n'' − ''o''(''n'') points. stated an even stronger bound of 1.235''n'' − ''o''(''n''), which remains the best lower bound known.〔 claimed that Kurowski's proof was erroneous, but later (after discussion with Jean Cardinal) retracted this claim; see (Explanation Supporting Kurowski's Proof ), D. Mondal, updated August 9, 2013.〕 Closing the gap between the known linear lower bounds and quadratic upper bounds remains an open problem.〔; ; .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Universal point set」の詳細全文を読む スポンサード リンク
|